package com.ycz.algorithm.utils.recursion;

import java.util.Stack;

/**
 * @author yancz
 * @ClassName RecursionUtil
 * @description: 递归：一种算法策略，通过函数调用自身来解决问题，过深的递归会导致调用栈溢出
 * @date 2024-08-27 16:41:16
 * @version: 1.0
 */
public class RecursionUtil {

    /*
     * @author yancz
     * @description // 递归求和（普通递归）
     * @date 2024/8/27 16:42
     * @param n
     * @return int
     **/
    static int recur(int n) {
        if (n == 1) return 1; // 终止条件
        int res = recur(n - 1); // 递归调用
        return n + res; // 返回结果
    }

    /*
     * @author yancz
     * @description 递归求和（尾递归）
     * @date 2024/8/27 16:54
     * @param n
     * @param res
     * @return int
     **/
    static int tailRecur(int n, int res) {
        if (n == 0) return res;
        return tailRecur(n - 1, res + n);
    }

    /*
     * @author yancz
     * @description 求斐波那契数列的第n个数，0,1,1,2,3,5,8,13,21,34,55，......
     * @date 2024/8/27 17:06
     * @param n
     * @return int
     **/
    static int fib(int n) {
        // 递归的终止条件是f(1)=0,f(2)=1
        if (n == 1 || n == 2) return n - 1;
        // 调用两次函数，产生两个分支，最终会产生一棵层数为n的递归树
        int res = fib(n - 1) + fib(n - 2);
        return res;
    }

    /*
     * @author yancz
     * @description 手动模拟栈调用
     * @date 2024/8/28 9:05
     * @param n
     * @return int
     **/
    static int forLoopRecur(int n) {
        Stack<Integer> stack = new Stack<>();
        int res = 0;
        for (int i = n; i > 0; i--) {
            // 入栈模拟递
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            // 出栈模拟归
            res += stack.pop();
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(recur(100));
        System.out.println(tailRecur(100, 0));
        System.out.println(fib(11));
        System.out.println(forLoopRecur(100));
    }

}
